{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3e62dcef-1e9b-476e-b23b-97ec7f83187d",
   "metadata": {},
   "source": [
    "# 选择排序"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d5b2c8f-c64d-435e-be39-569c9fcbf0fc",
   "metadata": {},
   "source": [
    "选择排序在冒泡排序的基础上做了改进，每次遍历列表时只做一次交换。要实现这一点，选择排序在每次遍历时寻找最大值，并在遍历完之后将它放到正确位置上。和冒泡排序一样，第一次遍历后，最大的元素就位；第二次遍历后，第二大的元素就位，依此类推。若给 n 个元素排序，需要遍历 n–1 轮，这是因为最后一个元素要到 n–1 轮遍历后才就位。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79f5d267-ca38-4a78-9474-89d69687dc5e",
   "metadata": {},
   "source": [
    "下图展示了完整的选择排序过程。每一轮遍历都选择待排序元素中最大的元素，并将其放到正确位置上。第一轮放好 93，第二轮放好 77，第三轮放好 55，依此类推。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0b7bd01-3fd5-41a8-a003-258bf22f6b0d",
   "metadata": {},
   "source": [
    "![选择排序](selection_sort.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2caa2cd-d9f4-49ad-851b-fd64745c08eb",
   "metadata": {},
   "source": [
    "下面代码给出了选择排序函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c8561a87-22fb-4ec3-8f89-fafcdcfabf3f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(alist):\n",
    "    for fillslot in range(len(alist)-1, 0, -1):\n",
    "        positionOfMax = 0\n",
    "        for location in range(1, fillslot+1):\n",
    "            if alist[location] > alist[positionOfMax]:\n",
    "                positionOfMax = location\n",
    "\n",
    "        temp = alist[fillslot]\n",
    "        alist[fillslot] = alist[positionOfMax]\n",
    "        alist[positionOfMax] = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1867e67e-0366-4755-b53d-899e609eadeb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before sorting: [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
      "after sorting: [17, 20, 26, 31, 44, 54, 55, 77, 93]\n"
     ]
    }
   ],
   "source": [
    "a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "print(f\"before sorting: {a_list}\")\n",
    "selection_sort(a_list)\n",
    "print(f\"after sorting: {a_list}\")\n",
    "assert a_list == sorted(a_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "74f36a68-1e0f-426b-af58-e1df789e3b7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint, seed\n",
    "seed(13)\n",
    "lst_to_sort = [randint(100, 999) for _ in range(1000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "0063490a-2e55-460e-9a21-e43e10109eab",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16.8 ms ± 111 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit selection_sort(lst_to_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "913f2dd8-c58f-4548-8eb1-1ed999cd0544",
   "metadata": {},
   "source": [
    "可以看出，选择排序算法和冒泡排序算法的比较次数相同，所以时间复杂度也是 $O(n^2)$ 。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69235ed1-f191-4b84-9765-ef80dee071c9",
   "metadata": {},
   "source": [
    "### 参考文档\n",
    "《Python数据结构与算法分析（第2版）》：5.3.2 选择排序"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
